package com.gitee.feizns.explore.data_structure.linked_list.singly.nextLargerNodes;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 链表中的下一个更大节点
 *
 * 给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
 *
 * 每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且  node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
 *
 * 返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
 *
 * 注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/next-greater-node-in-linked-list
 *
 * 输入：[2,1,5]
 * 输出：[5,5,0]
 *
 * @author feizns
 * @since 2019/11/1
 */
public class Main {

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextLargerNodes(create())));
    }

    private static ListNode create() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(2);
        ret.next.next = new ListNode(3);
        return ret;
    }

    public static int[] nextLargerNodes(ListNode head) {
        List<Integer> ret = new LinkedList<>();
        ListNode curt = head;
        Integer nextMax = null;
        while ( curt != null ) {
            if ( nextMax == null ) {
                nextMax = larger(curt.val, curt.next);
                ret.add(nextMax);
            } else if ( curt.val == nextMax ){
                ret.add(0);
                nextMax = null;
            } else
                ret.add(nextMax);
            curt = curt.next;
        }
        return ret.stream().mapToInt(Integer::intValue).toArray();
    }

    private static int larger(int val, ListNode node) {
        if ( node == null )
            return 0;
        int max = node.val;
        ListNode curt = node.next;
        while ( curt != null ) {
            if ( curt.val > max )
                max = curt.val;
            curt = curt.next;
        }
        return max > val ? max : 0;
    }

}
